package com.huang.other03;

import java.util.*;

public class SkipList {
    public SkipListEntry head; // 顶层的第一个元素
    public SkipListEntry tail; // 顶层的最后一个元素

    public int n; // 跳跃表中的元素个数

    public int h; // 跳跃表的高度
    public Random r; // 投掷硬币

    public SkipList() // 默认构造函数...
    {
        SkipListEntry p1, p2;

        p1 = new SkipListEntry(SkipListEntry.negInf, null);
        p2 = new SkipListEntry(SkipListEntry.posInf, null);

        head = p1;
        tail = p2;

        p1.right = p2;
        p2.left = p1;

        n = 0;
        h = 0;
        r = new Random();
    }

    /**
     * 返回 包含的元素个数
     */
    public int size() {
        return n;
    }

    /**
     * 跳跃表是否为空
     */
    public boolean isEmpty() {
        return (n == 0);
    }

    //在最下面一层，找到要插入的位置前面的那个key
    public SkipListEntry findEntry(String k) {
        SkipListEntry p;
        p = head;

        while (true) {
            /**
             * 一直向右找，例: k=34.
             * 10 ---> 20 ---> 30 ---> 40 ^ | p 会在30处停止
             * --------------------------------------------
             ***/
            while (p.right.key != SkipListEntry.posInf
                    && p.right.key.compareTo(k) <= 0) {
                p = p.right;
                //	System.out.println(">>>> " + p.key);
            }
            // 如果还有下一层，就到下一层继续查找
            if (p.down != null) {
                p = p.down;
                //System.out.println("vvvv " + p.key);
            } else
                break; // 到了最下面一层 就停止查找
        }
        //System.out.println("成功找到SkipListEntry-->" + p);
        return (p); // p.key <= k
    }

    /**
     * 返回和key绑定的值
     */
    public Integer get(String k) {
        SkipListEntry p;

        p = findEntry(k);

        if (k.equals(p.getKey())) {
            System.out.println("成功找到key:" + k + "对应的值为" + p.value);
            return (p.value);
        } else
            return (null);
    }

    /**
     * 放一个key-value到跳跃表中, 替换原有的并返回
     */
    public Integer put(String k, Integer v) {
        SkipListEntry p, q;
        int i;

        p = findEntry(k);

        if (k.equals(p.getKey())) {
            Integer old = p.value;
            p.value = v;
            return (old);
        }

        q = new SkipListEntry(k, v);
        q.left = p;
        q.right = p.right;
        p.right.left = q;
        p.right = q;

        i = 0; // 当前层 level = 0

        while (r.nextDouble() < 0.5) {

            //如果超出了高度，需要重新建一个顶层
            if (i >= h) {
                SkipListEntry p1, p2;

                h = h + 1;
                p1 = new SkipListEntry(SkipListEntry.negInf, null);
                p2 = new SkipListEntry(SkipListEntry.posInf, null);

                p1.right = p2;
                p1.down = head;

                p2.left = p1;
                p2.down = tail;

                head.up = p1;
                tail.up = p2;

                head = p1;
                tail = p2;
            }

            while (p.up == null) {
                p = p.left;
            }
            p = p.up;

            SkipListEntry e;

            e = new SkipListEntry(k, null);
            e.left = p;
            e.right = p.right;
            e.down = q;

            p.right.left = e;
            p.right = e;
            q.up = e;

            q = e; // q 进行下一层迭代
            i = i + 1; // 当前层 +1

        }
        n = n + 1;
        System.out.println("-----添加[" + k + "]后的跳跃表是:-----");
        printHorizontal();
        return (null); // No old value
    }
 
/*	public Integer remove(String key) {
		return (null);
	}*/

    /**
     * 根据键删除键值对
     *
     * @param key
     * @return
     * @author xxx 2017年2月14日 下午10:08:17
     * @since v1.0
     */
    public void remove(String key) {
        SkipListEntry p = findEntry(key);

        if (!p.getKey().equals(key)) {
            return;
        }
        //删除元素后重新关联，同时使被删除的对象游离，便于垃圾回收
        p.left.right = p.right;
        p.right.left = p.left;
        p.right = null;
        p.left = null;
        //自底向上，使所有键等于key的SkipListEntry对象左右两个方向的引用置空
        while (p.up != null) {
            p = p.up;
            p.left.right = p.right;
            p.right.left = p.left;
            p.right = null;
            p.left = null;
        }
        //自顶向下，使所有键等于key的SkipListEntry对象上下两个方向的引用置空
        while (p.down != null) {
            SkipListEntry temp = p.down;
            p.down = null;
            temp.up = null;
            p = temp;
        }
        /*
         * 删除元素后，如果顶层的链表只有head和tail两个元素，则删除顶层。
         * 删除顶层以后最新的顶层如果依然只有head和tail两个元素，则也要被删除，以此类推。
         */
        while (head.right.key == tail.key && h > 0) {
            SkipListEntry p1, p2;
            p1 = head.down;
            p2 = tail.down;
            head.right = null;
            head.down = null;
            tail.left = null;
            tail.down = null;
            p1.up = null;
            p2.up = null;
            head = p1;
            tail = p2;
            h = h - 1;
        }
        //成功移除一个元素，大小减1
        n = n - 1;
        System.out.println("-----删除[" + key + "]后的跳跃表是:-----");
        printHorizontal();
    }

    public void printHorizontal() {
        String s = "";
        int i;
        SkipListEntry p;

        p = head;

        while (p.down != null) {
            p = p.down;
        }

        i = 0;
        while (p != null) {
            p.pos = i++;
            p = p.right;
        }

        p = head;
        while (p != null) {
            s = getOneRow(p);
            System.out.println(s);

            p = p.down;
        }
    }

    //用了打印测试
    public String getOneRow(SkipListEntry p) {
        String s;
        int a, b, i;

        a = 0;

        s = "" + p.key;
        p = p.right;

        while (p != null) {
            SkipListEntry q;

            q = p;
            while (q.down != null)
                q = q.down;
            b = q.pos;

            s = s + " <-";

            for (i = a + 1; i < b; i++)
                s = s + "--------";

            s = s + "> " + p.key;

            a = b;

            p = p.right;
        }

        return (s);
    }

    //用了打印测试
    public void printVertical() {
        String s = "";
        SkipListEntry p;
        p = head;
        while (p.down != null)
            p = p.down;

        while (p != null) {
            s = getOneColumn(p);
            System.out.println(s);

            p = p.right;
        }
    }

    //用了打印测试
    public String getOneColumn(SkipListEntry p) {
        String s = "";
        while (p != null) {
            s = s + " " + p.key;
            p = p.up;
        }
        return (s);
    }
}